package com.school.chapter02.tree_;
import java.util.Stack;

public class ArithmeticExpressionTree {

        static String expression = "ab+cde+**";
        static Stack stack = new Stack();
        public static void main(String[] args) {
            Tree tree = createTree(expression);
            travTree(tree.root);
        }
        private static void travTree(Node node) {
            Node currentNode = node;
            if (currentNode != null) {
                travTree(currentNode.leftChild);
                travTree(currentNode.rightChild);
                System.out.print(node.element);
            }
        }

        private static Tree createTree(String expression) {//"ab+cde+**"
            for (int i = 0; i < expression.length(); i++) {
                char ch = expression.charAt(i);
                //如果是数就入栈，否则把运算符存入节点，出栈两个元素 ，分别作为该节点的左右子树，再将该节点入栈
                if (ch != '+' && ch != '-' && ch != '*' && ch != '/') {
                    Node node = new Node(ch);
                    stack.push(node);
                } else {
                    Node node = new Node(ch);
                    Node rightNode = (Node)stack.pop();
                    Node leftNode = (Node)stack.pop();
                    node.setLeftChild(leftNode);
                    node.setRightChild(rightNode);
                    stack.push(node);
                }
            }
            return new Tree((Node) stack.pop());
        }
    }

class Node {
    char element;
    Node leftChild;
    Node rightChild;
    Node(char element) {
        this.element = element;
    }
    void setLeftChild(Node leftChild) { this.leftChild = leftChild; }
    void setRightChild(Node rightChild) { this.rightChild = rightChild; }
}
class Tree {
    Node root;
    Tree(Node root) { this.root = root;}
}
